package 分治快排;

import java.awt.font.NumericShaper;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class 最小的k个数4 {
    //https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/
    //找前k大元素
    public static int[] inventoryManagement1(int[] stock, int cnt) {
        int[] ret = new int[cnt];
        if(cnt == 0) return ret;
        // 经全排序 就有至少它的NlogN
        // 堆排序 时间复杂度：N*logk
        Queue<Integer> queue = new PriorityQueue<>(cnt, (o1, o2) -> (Integer) o2 - o1); // o1 - o2默认是小根堆

//        System.out.println(queue.size()); // queue的size 指的是 里面现存的元素的个数}
        /*while (queue.size() < cnt) {
            queue.offer(stock[])
        }*/

        for (int i = 0; i < cnt; i++)
            queue.offer(stock[i]);
        for (int i = cnt; i < stock.length; i++) {
            if(stock[i] < queue.peek()) {
                queue.poll();
                queue.offer(stock[i]);
            }
        }
        for (int i = 0; i < cnt; i++)
            ret[i] = queue.poll();
        return ret;
    }
    public int[] inventoryManagement2(int[] stock, int cnt) {
        // 快速选择找元素 未经 全排序的至少N*logN地寻找，只排 三块式基准 下 去找n，时间复杂度N
        int[] ret = new int[cnt];
        return qfind(stock,0,stock.length - 1,cnt,ret,0);
    }
    public int[] qfind(int[] nums, int l, int r, int k, int[] ret, int index) {
        if(l == r) {
            ret[index++] = nums[l];
            return ret;
        }
        else if(l > r) return ret;
        int left = l - 1, right = r + 1, cur = l, key = nums[new Random().nextInt(r - l + 1) + l];
        while(cur < right) {
            if(nums[cur] < key) swap(nums,++left,cur++);
            else if(nums[cur] == key) cur++;
            else swap(nums,--right,cur);
        }
        int a = left - l + 1, b = right - left - 1, c = r - right + 1;
        // 这里如果 左区间、右区间没动 区间0元素 left = l - 1 < l，right = r + 1 > r，去递归调用 会越界的
        // 在递归进来的时候 判断排掉

        // a = k ∈ a + b >= k 且都是出结果，a = k情况 归到 a + b里面处理了
//        if(a < k) return qfind(nums,l,left,k,ret,index); // a = 0 < k，去递归传非法的左区间
        if(a > k) return qfind(nums,l,left,k,ret,index); // a = 0 < k，去递归传非法的左区间
        else if(a + b >= k) { // c = 0, a + b一定很大 进第二个if，没有去递归传右区间，没事
            for (int i = l; i < l + k; i++) {
                ret[index] = nums[i];
                index++;
            }
            return ret;
        }else {
            for (int i = l; i < right; i++) {
                ret[index++] = nums[i];
            }
            return qfind(nums,right,r,k - a - b,ret,index);
        }
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0,stock.length - 1,cnt);

        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            ret[i] = stock[i];
        }
        return ret;
    }

    //找元素(前k小)
    //全排好下去找 至少有排序的N*logN
    //只排 三块式基准下 去找N
    public void qsort(int[] nums, int l, int r, int k) {

        if(l >= r) return; // l==r时的递归区间 已经排好 不用排
        // l > r时的:
        // left=l-1 左指针没移动左块区间0元素 传左块区间的l、left进递归区间的 非法区间 不能排
        // right=r+1 右指针没移动右区间0元素 传右块区间的right、r进递归区间的 非法区间 不能排

        int key = nums[new Random().nextInt(r - l + 1) + l]; // l,r,left,right 都指向 递归数组在原数组的下标

        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if(nums[i] < key) swap(nums,left++,i++);
            else if(nums[i] == key) i++;
            else swap(nums,right--,i);
        }
        // [无序的左小块]、[排好的块等元素]、[无序的右大块]

        int a = left - l + 1, b = right - left - 1; // [无序的左小块]、[排好的块等元素] 的区间元素个数

        if(a > k) qsort(nums,l,left,k); // 要找的前k小元素的个数 < 无序左区间个数，去无序的左区间 找前k个小的数
        else if(a + b >= k) return; // a = k ∈ a + b >= k 出结果，要找的前k小元素的个数 !< 左区间个数, <= 左+中区间元素(包含了=左区间)，前k个元素已经是前k小的了(虽然是无序的)
        else qsort(nums,right,r,k - a - b); // 要找的前k小元素的个数 > 左+中区间元素，左+中已经是前k小的部分了，再去无序的右区间再排出前k-a-b个小的元素
    }

    public void swap(int[]nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(inventoryManagement1(new int[]{0,0,1,2,4,2,2,3,1,4},8)));
        最小的k个数4 最小的k个数41 = new 最小的k个数4();
        System.out.println(Arrays.toString(最小的k个数41.inventoryManagement2(new int[]{2,5,7,4},1)));
        System.out.println(Arrays.toString(最小的k个数41.inventoryManagement2(new int[]{0,2,3,6},2)));
    }
}
